package com.leetcode.No0015;

import org.junit.Test;

import java.util.*;

/**
 * @program: leetcode
 * @description: 三数之和
 * @author: wangzhihua
 * @date: 2021-06-01
 */
public class Solution {

	@Test
	public void test() {
		int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
		System.out.println(threeSum(nums));
	}

	public List<List<Integer>> threeSum(int[] nums) {
		ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
		if (nums == null || nums.length < 3) {
			return result;
		}

		Arrays.sort(nums);

		// 计算每个数字出现的次数
		Map<Integer, Integer> numCountMap = new HashMap<>();
		for (int num : nums) {
			Integer count = numCountMap.get(num);
			if (Objects.nonNull(count)) {
				numCountMap.put(num, count + 1);
			} else {
				numCountMap.put(num, 1);
			}
		}

		int n = nums.length;
		for (int i = 0; i < n; ++i) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}

			for (int j = i + 1; j < n; ++j) {
				if (nums[j] == nums[j - 1]) {
					continue;
				}

				int thirdNum = - nums[i] - nums[j];
				Integer countOfThirdNum = numCountMap.get(thirdNum);
				if (Objects.isNull(countOfThirdNum)) {
					continue;
				}

				if ((thirdNum == nums[i] || thirdNum == nums[j]) && countOfThirdNum > 1) {
					addNumsIntoResult(thirdNum, nums[i], nums[j], result);
				}
				if (thirdNum > nums[j] && countOfThirdNum > 0) {
					addNumsIntoResult(thirdNum, nums[i], nums[j], result);
				}
			}
		}

		if (Objects.nonNull(numCountMap.get(0)) && numCountMap.get(0) >= 3) {
			addNumsIntoResult(0, 0, 0, result);
		}

		return result;
	}

	void addNumsIntoResult(int a, int b, int c, List<List<Integer>> result) {
		ArrayList<Integer> tmpList = new ArrayList<Integer>();
		tmpList.add(a);
		tmpList.add(b);
		tmpList.add(c);
		result.add(tmpList);
	}

}
